%%%-------------------------------------------------------------------
%%% File    : p4.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description :
%%%           Find the largest palindrome made from the product of 
%%%           two 3-digit numbers.
%%%
%%% Created :  1 Dec 2008 by  <>
%%%-------------------------------------------------------------------
-module(p4).

%% API
-compile(export_all).

solution(Len) ->
    Size=Len*2,
    Min = trunc( math:pow(10, Len - 1)),
    Max = trunc(math:pow(10, Len) - 1),
    palindrom_iterator(fun(X)-> factor(X, Min,  Max) end, Size).

% A palindrom of N digits can be represented by a number of N/2 digits glued with its reversed copy if N is even or
% with its reversed copy without the first digit if N is odd.
% Example:
% 987789 = 987*1000 + 789
% 98789 = 987*100 + (789 rem 100)
%Returns a palindrom, created from a number half its length as described above
palindrom(Half, Pow10, even) ->
    Half*Pow10*10 + reverse(Half, Pow10);
palindrom(Half, Pow10, odd) ->
    Half*Pow10 + (reverse(Half, Pow10) rem Pow10).

%Iterates through all palindroms of a given size (number of digits) or less, applies the Fun function to each and returns the first result different than false (or null if no more left).
palindrom_iterator(Fun, Size) ->
    Half = (Size + 1) div 2,
    Pow10 = trunc(math:pow(10, Half - 1)),
    IsEven = case (Size rem 2) =:= 0 of
                 true -> even;
                 _ -> odd
             end,
    palindrom_iterator(Fun, Pow10*10, Pow10, IsEven).

palindrom_iterator(_, 0, _, _) -> null;
palindrom_iterator(Fun, Prev, Pow10, even) when Pow10 =:= Prev ->
    palindrom_iterator(Fun, Pow10*10 - 1 , Pow10, odd);
palindrom_iterator(Fun, Prev, Pow10, odd) when Pow10 =:= Prev ->
    palindrom_iterator(Fun, Pow10 - 1 , Pow10 div 10, even);
palindrom_iterator(Fun, Prev, Pow10, IsEven) ->
    Next = Prev - 1,
    P = palindrom(Next, Pow10, IsEven),
    case Fun(P) of
        false -> 
            palindrom_iterator(Fun, Next, Pow10, IsEven);
        Result ->
            Result
    end.

%Finds the largest factor of N between Min and Max. Returns {N, Factor, N div Factor} 
%or false if no factor exists. I.e finds 2 integers between Min and Max, K and L, 
%such that N = K*L
factor(N, Min, Max) ->
    Fun = fun(Current, Limit, _) when Current < Limit -> false;%not found
             (Current, Limit, Funself) when N rem Current =:= 0->
                  K = N div Current,
                  case K >= Min andalso K =< Max of
                      true -> {N, Current, N div Current};
                      _ -> Funself(Current - 1, Limit, Funself)
                  end;
             (Current, Limit, Funself) ->
                  Funself(Current - 1, Limit, Funself)
          end,
    %both factors need to be between Min and Max, so we iterate 
    %from the largest possible to the smallest one
    Start = max(N div (Max + 1), Min),
    End = min(N div Min, Max),
    Fun(End, Start, Fun).    

%Reverses the digits in the given number and returns the resulting number
reverse(N, Pow10) ->
    reverse(N, Pow10, 0).

reverse(0, _, Acc) ->
    Acc;
reverse(N, Pow10, Acc) ->
    reverse(N div 10, Pow10 div 10, Acc + (N rem 10)*Pow10).

%returns the maximum of two numbers
max(A, B) when A >= B -> A;
max(_A, B) -> B.
     
%return the minimum of two numbers
min(A, B) when A =< B -> A;
min(_A, B) -> B.
